package 图的遍历;
import java.util.LinkedList;
import java.util.Queue;
//import java.util.Scanner;

class Ergodic {
	public static void main(String[] args){
		//Scanner s = new Scanner(System.in);
		//int n = s.nextInt();
		//s.close();
		int [][] v = {
				{0,1,0,0,1},
				{0,0,1,0,0},
				{0,0,0,1,0},
				{1,1,0,0,0},
				{0,0,1,0,0}
			};
		char [] data = {'A','B','C','D','E'};
		Graph g = new Graph(v , data);
		g.InitIsVis();
		System.out.print("DFS: ");
		g.DFS(0);
		g.InitIsVis();
		System.out.print("\nBFS: ");
		g.BFS(0);
		g.FindIOd();
		System.out.print("\n结点：");
		for(char ch : g.data) {
			System.out.print(ch + " ");
		}
		System.out.println();
		System.out.print("入度：");
		for(int i : g.id) {
			System.out.print(i+" ");
		}
		System.out.print("\n出度：");
		for(int i : g.od) {
			System.out.print(i+" ");
		}
	}
}
class Graph{
	char [] data ;//图中节点的信息
	int[] id  ,od ;//图的入度和出度
	private boolean [] isVis;//记录某个节点是否被访问过
	private int [][] v;//记录图的连通关系
	public Graph(int[][] v ,char[] data){
		this.v = v;
		this.id = new int[v.length];
		this.od = new int[v.length];
		this.data = data;
		this.isVis = new boolean[v.length];
	}
	private void visit(int v){
		System.out.print(data[v]);
	}
	private int FristAdjVex(int v0){
		for(int i = 0; i<data.length; i++){
			if(v[v0][i] == 1) return i;
		}
		return -1;
	}
	private int NextAdjVex(int v0,int w){
		for(int i = w+1; i<data.length; i++){
			if(v[v0][i] == 1) return i;
		}
		return -1;
	}
	private boolean isVis(int v){
		return isVis[v];
	}
	public void InitIsVis(){
		for(int i = 0; i<isVis.length; i++) isVis[i] = false;
	}

	public void FindIOd() {
		for(int i = 0; i < v.length; i++) {
			for(int j = 0; j < v[i].length; j++) {
				if(v[i][j] == 1) {
					id[j] ++;
					od[i] ++;
				}
			}
		}
	}
	public void DFS(int v0){
		visit(v0);
		isVis[v0] = true;
		int w = FristAdjVex(v0);
		while(w != -1){
			if(!isVis(w)) 
				DFS(w);
			w = NextAdjVex(v0, w);
		}
	}
	public void BFS(int v0){
		visit(v0);
		isVis[v0] = true;
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v0);
		while(!queue.isEmpty()) {
			int v = queue.poll();
			int w = FristAdjVex(v);
			while (w != -1) {
				if(!isVis(w)) {
					System.out.print(data[w]);
					isVis[w] = true;
					queue.offer(w);
				}
				w = NextAdjVex(v, w);
			}
		}
	}
}